package 纯完全背包;

import java.util.Arrays;
import java.util.Map;

/**
 * @author: AirMan
 * @date: 2025/5/10 13:19
 * @description:
 * 给定一组物品，物品的重量和物品的价值给定
 * 每一个物品可以被无数次选择，给你一个容量为n的背包
 * 求这个背包最多能装下多大价值的东西
 */
public class Solution {
    public int completeBackpack(int[] weigh, int[] values, int bagSize) {
        // 纯完全背包问题
        // ① dp数组及其含义：dp[i][j]表示背包容量为i时，从0-i中无限选择物品，所能装下的最大价值数
        // ② 动态转移方程：dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weigh[i]] + value[i]);
        // ③ dp数组的初始化：第一列初始化为0，第一行根据物品0的重量和背包重量，能装就装
        // ④ 遍历顺序：先遍历物品再遍历背包，也可以先遍历背包再遍历物品
        // ⑤ 举例推导dp数组：输入weigh = [1,3,4] value = [10, 20, 65], bagSize = 4
        //     index:       0   1   2   3   4
        //                  0   15  30  45  60
        //                  0   15  30  45  60
        //                  0   15  30  45  65

        int[][] dp = new int[weigh.length][bagSize + 1];
        for (int i = weigh[0]; i <= bagSize; i++) {
            dp[0][i] = dp[0][i - weigh[0]] + values[0];
        }
        print(dp);

        for (int i = 1; i < weigh.length; i++) {
            for (int j = 0; j <= bagSize; j++) {
                if (j >= weigh[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weigh[i]] + values[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            print(dp);
        }

        return dp[weigh.length - 1][bagSize];
    }

    private void print(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("------------");
    }
}
